Multiplication of long integers modulo a prime number is a basic and repetitive operation that is used for so-called public key systems and various other applications. For an efficient usage of such applications, the execution time of the multiplication should be minimum. In consequence, the invention relates in particular to an apparatus for multiplying a first long integer entity with a second long integer entity modulo a prime number. Various methods and apparatuses have been proposed for the above through using a combination of multiplication and reduction operations. In particular, often the most significant part of the result has been used to actually effect the reduction. However, the present inventor has recognized that the developing of such most significant part will substantially delay the overall operation, especially, when the available hardware should be used at the highest possible duty cycle, in that a sequence of such multiplications must be executed in a contiguous manner.